package Dynamic_programming;

import org.apache.commons.lang3.StringUtils;
import org.junit.Test;

import java.util.*;

public class test011 {
    @Test
    public void xx() {
        String token = "";
        System.out.println(StringUtils.isNotEmpty(token));

    }
    public String replaceSpace(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        if (!StringUtils.isNoneEmpty(s)) {
            return s;
        }
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            if (a == ' ') {
                stringBuilder.append("%20");
            } else {
                stringBuilder.append(a);
            }
        }
        return stringBuilder.toString();
    }
    public String reverseLeftWords(String s, int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = n; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            stringBuilder.append(s.charAt(i));
        }
        return stringBuilder.toString();
    }
    public int findRepeatNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }
    public int search(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        Integer res = map.get(target);
        return res == null ? 0 : res;
    }
    public int missingNumber(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            if (l != nums[l]) {
                return l + 1;
            }
            if (r != nums[r]) {
                return r + 1;
            }
            l++;
            r--;
        }
        return -1;
    }
    @Test
    public void moveZeroes() {
        int[] nums = new int[]{1, 0, 3, 0, 4};
        int n = nums.length, l = 0, r = 0;
        while (r < n) {
            if (nums[r] != 0) {
                int temp = nums[r];
                nums[r] = nums[l];
                nums[l] = temp;
                l++;
            }
            r++;
        }
        for (int i : nums
        ) {
            System.out.println(i);
        }
    }
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) {
                return new int[]{l + 1, r + 1};
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
        return new int[]{-1, -1};
    }
    public ListNode middleNode(ListNode head) {
        int l = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            l++;
        }
        int mid = l / 2 + 1;
        ListNode res = head;
        for (int i = 1; i < mid; i++) {
            res = res.next;
        }
        return res;
    }
    public ListNode middleNode1(ListNode head) {
        ListNode l = head, r = head;
        while (r != null && r.next != null) {
            r = r.next.next;
            l = l.next;
        }
        return l;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode l = head, r = head;
        int len = 1;
        while (r != null) {
            if (len >= n) {
                l = l.next;
            }
            r = r.next;
        }
        l.next = l.next.next;
        return head;
    }
    public int maxSubarraySumCircular(int[] nums) {
        int maxVal = nums[0], minVal = nums[0],
                preMin = 0, preMax = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            preMax = Math.max(preMax + nums[i], nums[i]);
            maxVal = Math.max(maxVal, preMax);
            preMin = Math.min(preMin + nums[i], nums[i]);
            minVal = Math.min(minVal, preMin);
            sum += nums[i];
        }
        return Math.max(maxVal, sum - minVal == 0 ? maxVal : sum - minVal);
    }
    public int maxProfit(int[] prices) {
        int premax = 0, premin = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < premin) {
                premin = prices[i];
            } else if (prices[i] - premin > premax) {
                premax = prices[i] - premin;
            }
        }
        return premax;
    }
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int x = mat.length, y = mat[0].length;
        if (r * c != x * y) {
            return mat;
        }
        int[][] dp = new int[r][c];
        int index = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                dp[index / c][index % c] = mat[i][j];
                index++;
            }
        }
        return dp;
    }
    public void setZeroes(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    for (int k = 0; k < matrix[0].length; k++) {
                        matrix[i][k] = 0;
                    }
                    for (int k = 0; k < matrix.length; k++) {
                        matrix[k][j] = 0;
                    }
                }
            }
        }
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] != newColor) {
            dfs(image, sr, sc, newColor, image[sr][sc]);
        }
        return image;
    }
    public void dfs(int[][] image, int sr, int sc, int newColor, int oldColor) {
        if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length
                || image[sr][sc] != oldColor || newColor == oldColor) {
            return;
        }
        image[sr][sc] = newColor;
        dfs(image, sr - 1, sc, newColor, oldColor);
        dfs(image, sr, sc - 1, newColor, oldColor);
        dfs(image, sr + 1, sc, newColor, oldColor);
        dfs(image, sr, sc + 1, newColor, oldColor);
    }
    public void floodFill1(int[][] image, int sr, int sc, int newColor) {
        int[] dx = {1, 0, 0, -1};
        int[] dy = {0, 1, -1, 0};
        int currColor = image[sr][sc];
        if (currColor == newColor) {
            return;
        }
        int n = image.length, m = image[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                    queue.offer(new int[]{mx, my});
                    image[mx][my] = newColor;
                }
            }
        }
        return;
    }
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, dfs(grid, i, j));
                }
            }
        }
        return max;
    }
    public int dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0 || x > grid.length - 1 || y > grid[0].length - 1 || grid[x][y] == 0) {
            return 0;
        }
        grid[x][y] = 0;
        int sum = 1;
        sum += dfs(grid, x - 1, y);
        sum += dfs(grid, x + 1, y);
        sum += dfs(grid, x, y - 1);
        sum += dfs(grid, x, y + 1);
        return sum;

    }
    public void reverseString(char[] s) {
        int l = 0, r = s.length - 1;
        while (l < r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
    public String reverseWords(String s) {
        String[] strings = s.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strings.length; i++) {
            char[] temp = strings[i].toCharArray();
            int l = 0, r = temp.length - 1;
            while (l < r) {
                char temp1 = temp[l];
                temp[l] = temp[r];
                temp[r] = temp1;
                l++;
                r--;
            }
            for (char p : temp) {
                stringBuilder.append(p);
            }
            stringBuilder.append(" ");
        }
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        return stringBuilder.toString();
    }
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int ll = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] > target) {
                ll = i - 1;
                break;
            }
        }
        int l = 0, r = matrix[0].length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (matrix[ll][mid] < target) {
                l++;
            } else if (matrix[ll][mid] > target) {
                r--;
            } else {
                return true;
            }
        }
        return false;
    }
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (numbers[mid] < numbers[r]) {
                r = mid;
            } else if (numbers[mid] > numbers[r]) {
                l++;
            } else {
                r--;
            }
        }
        return numbers[l];
    }
    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }
        Map<Character, Integer> map = new HashMap<>();
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            int ll = map.get(s.charAt(i));
            if (ll == 1) {
                return s.charAt(ll);
            }
        }
        return ' ';
    }
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[]{};
        }
        Queue<TreeNode> listNodes = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        listNodes.add(root);
        while (!listNodes.isEmpty()) {
            TreeNode node = listNodes.poll();
            list.add(node.val);
            if (node.left != null) {
                listNodes.add(node.left);
            }
            if (node.right != null) {
                listNodes.add(node.right);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
    @Test
    public void ll() {
         /*  ListNode head=new ListNode(1,new ListNode(
        2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        System.out.println(middleNode(head));*/
         /*      System.out.println(maxSubarraySumCircular(new int[]{1, -2, 3, -2}));
        int[][]image=new int[][]{
                {1,1,1}, {1,1,0}, {1,0,1}
        };
          floodFill1(image, 1, 1, 2);
        for (int i = 0; i <image.length ; i++) {
            for (int j = 0; j <image[0].length ; j++) {
                System.out.print(image[i][j]+" ");
            }
            System.out.println();
        }*/
         /* System.out.println(findNumberIn2DArray(new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        }, 5));*/
        //System.out.println(minArray(new int[]{3, 4, 5, 1, 2}));
        isSymmetric(new TreeNode(3,
                new TreeNode(9, new TreeNode(15, null, null), new TreeNode(7, null, null)),
                new TreeNode(9, new TreeNode(15, null, null), new TreeNode(7, null, null))));
    }
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        boolean flag = true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            if (flag) {
                for (int i = queue.size(); i > 0; i--) {
                    TreeNode node = queue.poll();
                    list.add(node.val);

                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                flag = false;
            } else {
                for (int i = queue.size(); i > 0; i--) {
                    TreeNode node = queue.poll();
                    list.add(node.val);

                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                flag = true;
            }
            lists.add(list);
        }
        return lists;
    }
    public TreeNode mirrorTree(TreeNode root) {
        change(root);
        return root;
    }
    public void change(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        change(root.left);
        change(root.right);
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null || root.left.val != root.right.val) {
            return false;
        }
        boolean res = find(root.left, root.right);
        return res;
    }
    private boolean find(TreeNode left, TreeNode right) {
        if ((left == null && right != null) || (left != null && right == null)) {
            return false;
        }
        if ((left!=null&&right!=null)&&(left.val != right.val)) {
            return false;
        }
        if(left==null&&right==null){
            return true;
        }
        return find(left.left,right.left)&&find(left.right,right.right);
    }
    public int firstUniqChar1(String s) {
    Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for (int i = 0; i < s.length(); i++) {
            int c=map.get(s.charAt(i));
            if(c==1){
                return i;
            }
        }
    return -1;
    }
    public boolean canConstruct(String ransomNote, String magazine) {
    int[] chars=new int[128];
        for (int i = 0; i <magazine.length() ; i++) {
            chars[magazine.charAt(i)]+=1;
        }
        for (int i = 0; i <ransomNote.length() ; i++) {
            int i1=chars[ransomNote.charAt(i)]--;
            if(i1==0){
                return false;
            }
        }
        return true;
    }
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        if(head.val==Integer.MAX_VALUE){
            return true;
        }
        head.val=Integer.MAX_VALUE;
        return hasCycle(head.next);
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1==null||list2==null){
        return list1==null? list2:list1;
    }
    ListNode head=new ListNode(0);
    ListNode res=head;
    while (list1!=null||list2!=null){
        if(list1.val<=list2.val){
            head.next=list1;
            list1=list1.next;
        }else {
            head.next=list2;
            list2=list2.next;
        }
        head=head.next;
    }
    if(list1!=null){
        head.next=list1;
    }
    if(list2!=null){
        head.next=list2;
    }
    return res.next;
    }
    public ListNode removeElements(ListNode head, int val) {
    if(head==null){
        return head;
    }
    ListNode res=new ListNode();
    res.next=head;
    ListNode pre=res;
    while (head!=null){
        if(head.val==val){
            pre.next=head.next;
        }
        pre=pre.next;head=pre.next;
    }
    return res.next;
    }
    public int minOperations(int[] nums) {
        int ret = 0, maxn = 0;
        for (int num : nums) {
            maxn = Math.max(maxn, num);
            while (num != 0) {
                if ((num & 1) != 0) {
                    ret++;
                }
                num >>= 1;
            }
        }
        if (maxn != 0) {
            while (maxn != 0) {
                ret++;
                maxn >>= 1;
            }
            ret--;
        }
        return ret;
    }
    public int maxPower(String s) {
        int max=1;
        int len=1;
        char a1=s.charAt(0);
        for (int i = 1; i < s.length(); i++) {
            char temp=s.charAt(i);
            if(temp==a1){
                len++;
                a1=temp;
            }else {
                max=Math.max(max,len);
                len=1;
            }
        }
        return max;
    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null&&root2==null){
            return null;
        }
        if(root1==null||root2==null){
            return root1==null?root2:root1;
        }
        root1.val+=root2.val;
        mergeTrees(root1.left,root2.left);
        mergeTrees(root1.right,root2.right);
        return root1;
    }
    public Node connect(Node root) {
        if(root==null){
            return root;
        }
    Queue<Node> queue=new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        int size=queue.size();
        for (int i = 0; i <size ; i++) {
            Node temp=queue.poll();
            if(i<size-1){
                temp.next=queue.peek();
            }
            if(temp.left!=null){
                queue.add(temp.left);
            }
            if(temp.right!=null){
                queue.add(temp.right);
            }
        }
    }
    return root;
    }
    public ListNode reverseList(ListNode head) {
    if(head==null){
        return head;
    }
    ListNode pre=null;
    while (head!=null){
        ListNode next=head.next;
        head.next=pre;
        pre=head;
      head=next;
    }
    return pre;
    }
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode pre=head;
        head=pre.next;
        ListNode res=head;
        while (head!=null){
            ListNode next=head.next;
            if(pre.val==head.val){
                pre.next=next;
            }else {
                pre=head;
            }
            head=next;
        }
        return res;
    }
    public int fib(int n) {
   final int MOD=1000000007;
    if(n<2){
        return n;
    }
    int res=0,f0=0,f1=1;
        for (int i =2; i < n; i++) {
            res=f0+f1;
            f0=f1;
            res%=MOD;
            f1=res;
        }
        return res%MOD;
    }
    public int numWays(int n) {
        int MOD=1000000007;
    if(n==0){
        return 0;
    }
    if(n<3){
        return n;
    }
        int f1=1,f2=2,res=0;
        for (int i = 0; i <n ; i++) {
            res=f1+f2;
            f1=f2;
            res%=MOD;
            f2=res;
        }
        return res%MOD;
    }
    public int maxProfit1(int[] prices) {
        if(prices==null||prices.length==0){
            return 0;
        }
    int min=Integer.MAX_VALUE;
    int max=Integer.MIN_VALUE;
        for (int i = 0; i <prices.length; i++) {
            if(prices[i]<min){
                min=prices[i];
            }
            max=Math.max(max,prices[i]-min);
        }
        return max;
    }
    public int distributeCandies(int[] candyType) {
    Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < candyType.length; i++) {
            map.put(candyType[i],map.getOrDefault(candyType[i],0)+1);
        }
        int mid=candyType.length/2;
        return map.size()>mid? mid:map.size();
    }
    public boolean isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
    public int longestSubsequence(int[] arr, int difference) {
        int ans = 0;
        Map<Integer, Integer> dp = new HashMap<Integer, Integer>();
        for (int v : arr) {
            dp.put(v, dp.getOrDefault(v - difference, 0) + 1);
            ans = Math.max(ans, dp.get(v));
        }
        return ans;
    }
    public int missingNumber1(int[] nums) {
            int res = nums.length;
            for (int i = 0; i < res; ++i){
                res = res ^ i ^ nums[i];
            }
            return res;
    }
    public int maxCount(int m, int n, int[][] ops) {
        if(ops==null||ops.length==0){
            return 0;
        }
        int x=Integer.MAX_VALUE;int y=Integer.MAX_VALUE;
        for (int i = 0; i <ops.length ; i++) {
            if(ops[i]==null){
                continue;
            }
            for (int j = 0; j <2 ; j++) {
                if(ops[i][0]<x){
                    x=ops[i][0];
                }
                if(ops[i][1]<y){
                    y=ops[i][1];
                }
            }
        }
        return (x*y);
    }
    public String getHint(String secret, String guess) {
    Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i <secret.length() ; i++) {
            map.put(secret.charAt(i),map.getOrDefault(secret.charAt(i),0)+1);
        }
        int x=0,y=0;
        for (int i = 0; i <secret.length() ; i++) {
            if(secret.charAt(i)==guess.charAt(i)&&(map.get(guess.charAt(i))!=0)){
                x++;
                map.put(guess.charAt(i),map.get(guess.charAt(i))-1);
            }else if(map.get(guess.charAt(i))!=0){
                y++;
                map.put(guess.charAt(i),map.get(guess.charAt(i))-1);
            }
        }
    return x+"A"+y+"B";
    }
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int time=timeSeries[1],sum=0,x=time+duration-1;
        for (int i = 1; i <timeSeries.length ; i++) {
            if(timeSeries[i]>=x){
                sum+=duration;

            }else{
                sum+=timeSeries[i]-time;
            }
            x=timeSeries[i]+duration-1;
            time=timeSeries[i];
        }
        return sum;
    }
    public boolean detectCapitalUse(String word) {
        boolean flag=true;boolean flag1=true;
        boolean first=false;
        if(word.charAt(0)<='Z'&&word.charAt(0)>='A'){
            first=true;
        }
        for (int i = 1; i <word.length() ; i++) {
            flag=flag&(word.charAt(i)<='Z'&&word.charAt(i)>='A');
            flag1=flag1&(word.charAt(i)<='z'&&word.charAt(i)>='a');
        }
        if((flag&first)||(first&&flag1)||(!first&&flag1)){
            return true;
        }
        return false;
    }
    public String[] findRelativeRanks(int[] score) {
         int[] ints = Arrays.copyOf(score, score.length);
         Arrays.sort(new int[][]{ints},Collections.reverseOrder());
         String[] res=new String[score.length];
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j <res.length ; j++) {
                if(i==0&&ints[i]==score[j]){
                        res[j]="Gold Medal";
                }
             else    if(i==1&&ints[i]==score[j]){
                    res[j]="Silver Medal";
                }
              else   if(i==2&&ints[i]==score[j]){

                    res[j]="Bronze Medal";
                }else if(ints[i]==score[j]){
                  res[j]= String.valueOf(i+1);
                }
            }
        }
        return res;
    }
    public boolean isValid(String s) {
    if(s==null||s.length()==0){
        return false;
    }
        for (int i = 0; i < s.length(); i++) {
            if(s.contains("()")){
               s= s.replace("()","");
            }
            if(s.contains("[]")){
                s=s.replace("[]","");
            }
            if(s.contains("{}")){
               s= s.replace("{}","");
            }
        }
       return "".equals(s);
    }
    public int orchestraLayout(int num, int xPos, int yPos) {
        //先找到它在第几层
        //计算出层开始时的编号
        //算出对应乐器编号
        long l = Math.min(Math.min(xPos, num - 1 - xPos), Math.min(yPos, num - 1 - yPos));
        long pre = (num * l - l * l) * 4 % 9;
        long ans = 0;
        if(xPos == l){
            ans = pre + (yPos - l + 1);
            ans %= 9;
        }else if(num - 1 - yPos == l){
            ans = pre + num - (l * 2) - 1 + (xPos - l + 1);
            ans %= 9;
        }else if(num - 1 - xPos == l){
            ans = pre + (num - (l * 2) - 1) * 2 + (num - l - yPos);
            ans %= 9;
        }else{
            ans = pre + (num - (l * 2) - 1) * 3 + (num - l - xPos);
            ans %= 9;
        }
        return (int)ans == 0 ? 9 : (int) ans;
    }
    public int maxSubArray(int[] nums) {
    if(nums==null||nums.length==0){
        return 0;
    }
    int dp[]=new int[nums.length];
    dp[0]=nums[0];
    int max=dp[0];
        for (int i = 1; i <nums.length ; i++) {
            if(dp[i-1]>=0){
                dp[i]=dp[i-1]+nums[i];
            }else {
                dp[i]=nums[i];
            }
            max=Math.max(dp[i],max);
        }
        return max;
    }
    public int maxValue(int[][] grid) {
    int [][] dp=new int[grid.length][grid[0].length];
    dp[0][0]=grid[0][0];
        for (int i = 1; i <dp.length ; i++) {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i <dp[0].length ; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i <dp.length ; i++) {
            for (int j = 1; j <dp[0].length ; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
    public int[] twoSum1(int[] numbers, int target) {
    int l=0,r=numbers.length-1;
    while (l<r){
        int sum=numbers[l]+numbers[r];
        if(sum<target){
            l++;
        }else if(sum>target){
            r--;
        }else {
            return new int[]{l+1,r+1};
        }
    }
    return new int[]{};
    }
    @Test
    public void xx1() {
        //System.out.println(minOperations(new int[]{1, 5}));
//        System.out.println(multiply("2", "3"));
        System.out.println(Arrays.toString(getFolderNames(new String[]{"onepiece",
                "onepiece(1)", "onepiece(2)", "onepiece(3)", "onepiece"})));
    }
    public String multiply(String num1, String num2) {
        if(num1==null||num1.length()==0){
            return num2;
        }
        int cut1=0,cut2=0;
        for (int i = 0; i <num1.length() ; i++) {
            if(num1.charAt(i)=='0'){
                cut1++;
            }else {
                break;
            }
        }
        for (int i = 0; i <num2.length() ; i++) {
            if(num2.charAt(i)=='0'){
                cut2++;
            }else {
                break;
            }
        }
        num1=num1.substring(cut1,num1.length());
        num2=num2.substring(cut2,num2.length());
        int sum1=0,mot=1;
        for (int i = num1.length()-1; i >=0; i--) {
            int x=(num1.charAt(i)-'0')*mot;
            int mot1=1,sum=0;
            for (int j = 0; j <num2.length() ; j++) {
                sum+=((num2.charAt(j)-'0')*x)*mot1;
                mot1*=10;
            }
            sum1=sum1*mot+sum;
            mot*=10;
        }
        return String.valueOf(sum1);
    }
    public String[] getFolderNames(String[] names) {
    Map<String,Integer> map=new HashMap<>();
        for (int i = 0; i <names.length ; i++) {
            if(map.containsKey(names[i])){
               String x=names[i]+"("+map.get(names[i])+")";
                int ll=map.get(x);
                while (map.containsKey(x)){
                    ll++;
                    x=names[i]+"("+(ll)+")";
                }
                names[i]=x;
            }
            map.put(names[i],map.getOrDefault(names[i],0)+1);
        }
        return names;
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
    Arrays.sort(nums);
        for (int i = 0; i <k ; i++) {
        nums[i]=-1*nums[i];
            System.out.println(nums[i]);
        }
        Arrays.sort(nums);
        int sum=0;
        for (int i = 0; i <nums.length ; i++) {
            if(nums[i]>0){
                sum+=nums[i];
                System.out.println(nums[i]);
            }
        }
        return sum;
    }
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
    if(list1==null||list2==null){
        return list1==null? list2:list1;
    }
    ListNode res=new ListNode();
    ListNode p=res;
        while (list1!=null||list2!=null){
            if(list1.val>list2.val){
                p.next=list2;
                list2=list2.next;
            }else {
                p.next=list1;
                list1=list1.next;
            }
            p=p.next;
        }
        if(list1==null||list2==null){
            p.next= list1==null? list2:list1;
        }
        return res.next;
    }
    public ListNode reverseList1(ListNode head) {
    if(head==null){
        return head;
    }
    ListNode pre=null;
    while (head!=null){
        ListNode next=head.next;
        head.next=pre;
        pre=head;
        head=next;
    }
    return pre;
    }
    public int orangesRotting(int[][] grid) {
    Queue<int[]> queue=new LinkedList<>();
    int x=grid.length;int y=grid[0].length;
    int res=0;
    int [] X=new int[]{1,0,-1, 0};
    int [] Y=new int[]{0,1,0,-1};
        for (int i = 0; i <x; i++) {
            for (int j = 0; j <y ; j++) {
                if(grid[i][j]==2){
                    queue.add(new int[]{i,j,0});
                }
            }
        }
        while (!queue.isEmpty()){
            int[] core=queue.remove();
            int l=core[0];
            int m=core[1];
            int mo=core[2];
            for (int i = 0; i <4 ; i++) {
                int x1=l+X[i]; int x2=m+Y[i];
                if(0<=x1&&x1<x&&0<=x2&&x2<y&&grid[x1][x2]==1){
                    grid[x1][x2]=2;
                    int core1= x1*y+x2;
                queue.add(new int[]{x1,x2,mo+1});
                res=mo+1;
                }
            }
        }
        for (int[] l:grid) {
            for (int ll1:l) {
                if(ll1==1){
                    return -1;
                }
            }
        }
        return res;
    }
}
 class ListNode {
     int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

     @Override
     public String toString() {
         return "ListNode{" +
                 "val=" + val +
                 ", next=" + next +
                 '}';
     }
 }
 class TreeNode {
    int val;
      TreeNode left;
     TreeNode right;

     public TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }

     public TreeNode(int val) {
         this.val = val;
     }

     @Override
     public String toString() {
         return "TreeNode{" +
                 "val=" + val +
                 ", left=" + left +
                 ", right=" + right +
                 '}';
     }
 }
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
class MapSum {

    public MapSum() {

    }

    public void insert(String key, int val) {

    }

    public int sum(String prefix) {
return -1;
    }
}
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
int top;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void push(int x) {
        top=x;
    if(stack2.isEmpty()){
        stack2.push(x);
    }
    while (!stack1.isEmpty()){
        stack2.push(stack1.pop());
    }
    while (!stack2.isEmpty()){
        stack1.push(stack2.pop());
    }
    }

    public int pop() {
   return stack1.pop();
    }

    public int peek() {
    return top;
    }

    public boolean empty() {
    return stack1.isEmpty();
    }
}
